#1.直接插入排序
# def InsertSort(list_):
#     for i in range(1,len(list_)):           #从列表的第二个元素开始找
#         j = i-1                             #先定位第i个元素的前一个元素
#         if list_[j] > list_[i]:             #如果前一个元素比第i个元素大
#             temp = list_[i]                 #前一个元素比i元素大，所以i元素需要往前插入，故先把list_[i]赋值给一个临时变量
#             list_[j+1] = list_[j]           #i元素插入后，其前一个元素即j元素肯定向后位移一位
#             # 继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
#             j -= 1
#             while j >= 0 and list_[j] > temp:
#                 list_[j+1] = list_[j]
#                 j -= 1
#             list_[j+1] = temp     #只要找到比temp小的元素，就将temp插入到其后一位(原本其后面一位元素已经右移走掉了)，
#                                   #或者i元素前面所有元素都比它大，则j循环到-1时，temp被赋值给了list_[0]即达到列表首位
#     return list_
#
# print(InsertSort([30,80,20,60,10,50,40,70,90]))




#2、冒泡排序
# list1 = [1,2,4,6,3,5,9,8,7]
# for i in range(len(list1)-1): #循环遍历从0开始到倒数第二个元素下标
#     for j in range(len(list1)-1-i):  #循环遍历从0开始，每次循环将最大数放到最末尾
#         if list1[j] > list1[j+1]:  #判断两个相邻数的大小，大的往后面排，小的往前面排
#             list1[j],list1[j+1] = list1[j+1],list1[j]
# print(list1)



#3.快速排序
# def quicksort(array):
#     if len(array) < 2:
#         return array
#     else:
#         pivot = array[0]
#         less = [i for i in array[1:] if i<= pivot]
#         greater = [i for i in array[1:] if i > pivot]
#         return quicksort(less) + [pivot] + quicksort(greater)
# b = quicksort([5,11,3,9,8,2,6,7])
# print(b)



#4.直接选择排序
# def SelectSort(list_):                      #保存当前最小的，初始化的时候，认为当前为最小，向后搜索比它小的元素
#     for i in range(len(list_)-1):
#         temp = i                           #把当前元素脚标赋给临时变量
#         for j in range(i+1,len(list_)):    #将当前元素与后续元素依次比较
#             if list_[j] < list_[temp]:     #入后后面元素比当前元素还要小
#                 temp = j                   #交换脚标
#         list_[i],list_[temp] = list_[temp],list_[i]    #交换值
#     return list_
#
# print(SelectSort([5,11,3,9,8,2,6,7]))
